

// var arr = [10,16,55,7,32,3,0,5,69,2,3,78,3]
var arr = [3,2,1,5,4,6]

// 快速排序
// 时间复杂度：
// 空间复杂度；
function quickSort(arr, start, end){
    if(end-start===0) return [arr[start]]

    let flag = start
    let i = start + 1
    let j = end

    while(i < j){
        while(flag < j){
            if(arr[flag] > arr[j]){
                flag = swap(arr, j--, flag)
                break
            }
            j--
        }

        while(flag > i){
            if(arr[flag] < arr[i]){
                flag = swap(arr, i++, flag)
                break
            }
            i++
        }
    }


    const left = quickSort(arr, start, flag)
    const right = quickSort(arr, flag+1, end)

    return left.concat(right)

}


function swap(obj, i, base){
    let t = obj[i]
    obj[i] = obj[base]
    obj[base] = t
    return i
}


function quickSort2(arr) {
    if(arr.length<=1) return arr

    let flag = arr[0]
    let list = arr.slice(1, arr.length)

    let left = list.filter(num => num<=flag)
    let right = list.filter(num => num>flag) 

    return quickSort2(left).concat([flag]).concat(quickSort2(right))

}


// console.log(insertSort(arr, 0, arr.length - 1))



// 归并排序
// 时间复杂度：O(nlogn)
// 空间复杂度；O(n)
function mergeSort(arr) {
    if(arr.length <= 1) return arr
    if(arr.length == 2){
        if(arr[0] > arr[1]){
            return [arr[1], arr[0]] 
        }
        return arr
    } 

    const mid = Math.floor(arr.length/2)
    const left = mergeSort(arr.slice(0, mid))
    const right = mergeSort(arr.slice(mid, arr.length))

    let list = []

    while(left.length > 0 && right.length > 0){
        if(left[0]<right[0]){
            list.push(left.shift())
        }
        else {
            list.push(right.shift())
        }
    }

    while(left.length > 0){
        list.push(left.shift())
    }

    while(right.length > 0){
        list.push(right.shift())
    }

    return list
}
console.log("mergeSort:", mergeSort(arr))


// 冒泡排序：N小的时候使用，所以就暂时不考虑空间复杂度了
// 时间复杂度：
// 空间复杂度；
function bubbleSort(arr) {

    let i = 0
    while(i < arr.length-1){
        let j = 1
        while(j < arr.length-i){
            if(arr[j] < arr[j-1]){
                swap(arr, j-1, j)
            }
            j++
        }
        i++
    }
    return arr
}



// 插入排序：N小的时候使用，所以就暂时不考虑空间复杂度了
// 选出数组中最小的一个数字，然后插入到另外一个数组
function insertSort (arr) {
    const nArr = []

    let length = arr.length

    while(nArr.length < length){
        let min = 0
        let i = 0
        while(i < arr.length){
            if(arr[i] <= arr[min]){
                min = i
            }
            i++
        }
        nArr.push(arr[min])
        arr.splice(min, 1)
    }

    return nArr
}




// 版本号排序

const vArr = ['0.1.1', '2.3.3', '0.302.1', '4.2', '4.3.5', '4.3.4.5']


// 树形结构转数组
let tree = {
    "id": 1,
    "text": "节点1",
    "children": [
        {
            "id": 2,
            "text": "节点1_1",
            "children": [
                {
                    "id": 4,
                    "text": "节点2_1"
                },
                {
                    "id": 5,
                    "text": "节点2_2"
                }
            ]
        },
        {
            "id": 3,
            "text": "节点1_2"
        }
    ]
}

function transferArr (tree, parentId = -1) {
    arr.push({
        id: tree.id,
        text: tree.text,
        parentId
    })

    if(tree.children){
        tree.children.map(treeNode => {
            arr.concat(transferArr(treeNode, tree.id))
        })
    }

    return arr
}

// console.log(transferArr(tree))

// 数组转树形结构
let treeArr = [
    {
        id: 1,
        text: '节点1',
        parentId: 0 //这里用0表示为顶级节点
    },
    {
        id: 2,
        text: '节点1_1',
        parentId: 1 //通过这个字段来确定子父级
    },
    {
        id: 3,
        text: '节点1_2',
        parentId: 1
    },
    {
        id: 4,
        text: '节点2_1',
        parentId: 2
    },
    {
        id: 5,
        text: '节点2_2',
        parentId: 2
    }
]

function transfer(arr) {
    arr.forEach(node => {
        let parent = arr.find(item => item.id === node.parentId)

        if(parent){
            parent.children = parent.children || []
            parent.children.push(node)
        }
    })

    return arr[0]
}

// console.log(JSON.stringify(transfer(treeArr)))



// 大数相加

let a = "9007199254740991";
let b = "1234567899999999999";

function bigNumAdd (a, b) {


}


// 上亿条数据中查找最大的数

// let bigArr = []
// let i = 0
// while(i<100000000){
//     bigArr.push(Math.random()*100)
//     i++
// }
// console.log(bigArr)



// 字符串压缩
function zipString () {

    const string = "aaabcddddff"
    let num = 1;
    let i = 1
    const length = string.length

    let str = string[0]

    while(i<length){
        if(string[i] === string[i-1]){
            num ++
        }
        else{ 
            str = str + num + string[i]
            num = 1
        }
        i++
    }
    str += num

    console.log("str:", str)
}

// 测试
// zipString()
